Many passenger vehicles now incorporate an integrated communication system. A Vehicle Communication Unit (VCU) used in conjunction with a Wide Area Network (WAN) such as a cellular telephone network or a satellite communication system allows for a variety of fee-based subscription services to be provided in a mobile environment. The VCU is typically a vehicle telematics device including a cellular radio, satellite transceiver, a wireless access point transceiver adhering to IEEE 802.11 or similar wireless communication standards, and global positioning capabilities. Communication through a carrier service may be initiated at the VCU at turn-on or through manual or voice command phone number entry. A radio communication link is established between the VCU and a node of a wireless LAN or WAN in the vicinity of the VCU to provide an additional communications channel through a wireless mobile ad hoc network (MANET).
A wireless mobile ad hoc network provides communication through a dynamic network formed of wireless access point nodes within radio transmission range of one another. The mobile wireless access point nodes exchange information among each other (e.g. location, velocity, etc.) to route information, such as data packets, within the ad hoc network. An information dissemination algorithm provides a communication protocol for information exchange within the MANET. A wireless access point node seeking to disseminate information (e.g. position information) to another wireless access point node invokes the information dissemination algorithm to facilitate communication between the nodes.
There are generally two routing paradigms for mobile ad hoc networks: topology-based and position-based. Topology-based routing protocols use information about the links that form the network (connectivity) to forward a packet from a source node to a destination node. The topology-based routing protocols can be further classified into proactive and on-demand. On-demand routing protocols are favorable in MANETs due to their low overhead compared to proactive (table-driven) counterparts, since multi-hop routes must be discovered and maintained only when needed. This advantage comes at the expense of the latency incurred in the initial route setup (discovery) phase.
The operation of topology-based on-demand protocols starts with a route discovery phase in which a source node sends a route request (RR) message throughout the ad hoc network in order to establish a route to a destination node. Once the destination node receives the RR, it replies with a route confirm (RC) message through the discovered route. Most on-demand routing protocol proposals rely on flooding algorithms for RR dissemination. Flooding in an ad hoc network comprises broadcasting a communication to every node in the vicinity of the originating node. Afterwards, each node that successfully receives the broadcast packet re-broadcasts it to its respective neighbors. This process is repeated until the entire network is covered.
By contrast, position-based routing protocols depend solely on the physical location of the participating nodes, which alleviates some of the limitations of topology-based routing. A position based routing protocol instructs a node to forward a data packet to the neighbor closest to the destination without defining a complete path to the destination, i.e. the routing decisions are taken on a hop-by-hop basis. The main advantage is that it eliminates any delay incurred by the route discovery phase, since the packet forwarding decision is based solely on position information. In addition, any impact on the routing decision resulting from the mobility of intermediate nodes is largely reduced, since the routing decision does not depend on topology and is taken on a hop-by-hop basis. However, this advantage is gained at the expense of separate information dissemination algorithms that serve as the infrastructure for distributing location information among all nodes in the network. The above discussion illustrates that information dissemination is a fundamental element of the two main classes of routing protocols in MANETs, namely on-demand topology-based and position-based routing.
In MANETs, we introduce a metric of information dissemination performance known as “reachability”, which is defined as the percentage of times a node of interest is successfully located within the ad hoc network. Another MANET performance metric is delay, which is defined as the time incurred to locate a node. Other performance metrics include communication overhead (the total number of transmissions needed to achieve the dissemination task) and storage overhead (the average number of table entries per access point node).
One example of information dissemination, referred to above, is flooding. Flooding is very simple, however, it achieves very low reachability due to the so-called “broadcast storm problem”. The broadcast storm problem arises when all neighbors of a given node, say A, re-broadcast a packet sent by A. This, in turn, causes an excessive number of collisions at the multiple access control (MAC) layer. In addition, flooding-based algorithms are highly inefficient since they waste the system's bandwidth and energy resources unnecessarily. Presently known information dissemination algorithms for mobile ad hoc networks introduced in the literature are primarily based on flooding. Examples of flooding include Ad hoc on Demand Vector (AODV) and Dynamic Source Routing (DSR) techniques as described by E. Royer and C-K Toh, (“A Review of Current Routing Protocols for Ad-Hoc Mobile Wireless Networks,” IEEE Personal Communications Magazine, pp. 46-55, April 1999), and other protocols described by M. Mauve, J. Widmer and H. Hartenstein, (“A Survey on Position-based Routing in Mobile Ad Hoc Networks,” IEEE Network, pp. 30-39, November/December 2001). As discussed previously, flooding is highly inefficient due to the broadcast storm problem, as reported by J. Broch, et al., (“A Performance Comparison of Multi-hop Wireless Ad-hoc Networking Routing Protocols,” ACM MOBICOM, October 1998). In addition, flooding wastes system bandwidth and energy resources unnecessarily, such as, for instance, the so called “DREAM” system which uses table-based flooding for information dissemination (S. Basagni et al., “A Distance Routing Effect Algorithm for Mobility (DREAM),” ACM MOBICOM 1998). Thus, in the DREAM system proposal, each node would have to keep the information (e.g. position) of every other node in the network. It is evident that this approach is not scalable, and furthermore would be infeasible in an embedded system environment due to the large table data storage requirements.
In another proposal by Z. Haas and B. Liang, (“Ad Hoc Mobility Management with Uniform Quorum Systems,” IEEE/ACM Transactions on Networking, Vol.7, No.2, pp. 228-240, April 1999), the authors propose a quorum-based location service for ad hoc networks. Under this proposal, a subset of mobile nodes (that constitute a “virtual backbone”) are chosen to keep the position information of all other nodes. Although this protocol proposal could potentially reduce the dissemination overhead, a considerable amount of control overhead would be incurred in creating and maintaining the virtual backbone under mobility conditions.
Another article by J. Li et al., (“A Scalable Location Service for Geographic Ad Hoc Routing,” ACM MOBICOM 2000), proposes a hierarchical Grid location service. However, its applicability to the car-to-car networks environment is questionable due to the limited processing and storage constraints enforced by the embedded system implementation.
An article by M. Sun, et al., (“GPS-Based Message Broadcasting for Inter-vehicle Communication,” IEEE International Conference on Parallel Processing, 2000), describes the idea of border node (selective) flooding. The essence of the proposed algorithm is to select a number of neighbors, to re-broadcast a message, based on the neighbors' location relative to the sender. However, the algorithm proposed by M. Sun, et al., has two major limitations. First, it is not scalable since, for large networks, each vehicle would have to keep a huge table carrying the position information of all other vehicles; second, it is not optimized for arbitrary roadmaps with multiple intersecting roads. These limitations constitute major hurdles towards the utility and feasibility of the algorithm proposed by M. Sun, et al. in a car-to-car networks environment.
Presently known and proposed information dissemination algorithms lack scalability for dynamically changing node density, such as when node density cycles between many nodes and few nodes in a given time period. Furthermore, known algorithms are not optimized for arbitrary node location and consume memory resources that exceed the practical limitations of many embedded system designs. It is desirable, therefore, to provide a system and method for information dissemination in an ad hoc mobile network that overcomes these and other disadvantages.